package week_5.homework;

import java.util.Scanner;

//实现程序设计项目pp9.1，间隔排序法
/*间隔排序法比较的是位置间距为某个数量（i）的两个元素，i是小于n的一个数。
* 比如，第一个元素与第（i+1）个元素进行比较，第二个元素与第（i+2）个元素进行比较，
* 第n个元素将会和第（n-i）个元素比较，等等
* 当所有能比较的元素都已经得到比较后，这就完成了一次迭代。在下一轮迭代中，将i减少某个大于1的数量,并继续该过程直至i<1.*/
public class GapSort {
    public static <T extends Comparable<T>> void GapSort(T[] data) {
        int position = data.length - 1;
        int scan;
        Scanner gapnumber = new Scanner(System.in);
        System.out.println("请输入在间隔排序中你想实现的间隔数量(输入数字>=1)：");
        int i = gapnumber.nextInt();
        if (i <= 1)
            System.out.println("请输入大于等于1的数字");
        else {
            while (position >= 0 & i >= 1) {

                for (scan = 0; scan <= position - i; scan++) {
                    if (data[scan].compareTo(data[scan + i]) > 0)
                        swap(data, scan, scan + i);
                }//内循环里面是两个间隔确定的数字连续比较直到列表末尾
                position--;
                i--;
            }//外循环里面是一共进行内循环的次数，其次数与列表元素个数-1相等
        }
    }
    private static <T extends Comparable<T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
}
